﻿#pragma once
#include "Index.h"
/**
 * 二叉搜索树的最近公共祖先.
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
 * 2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
 * 3.所有节点的值都是唯一的。
 * 4.p、q 为不同节点且均存在于给定的二叉搜索树中。
 */
namespace BSTCommonAncestor
{
    class Question
    {
    public:
        virtual TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) =0;
    };

    class CommonNodeBetweenLists
    {
    public:
        /**
         * 转链表找公共节点问题:
         *	1、将从树根节点到p、q的路径转换为2条单链表
         *	2、翻转2条单链表后，就将问题转为找2条单链表的公共节点问题
         *	3、空间复杂度:O(树高) 时间复杂度:O(p链表长度+q链表长度)
         */
        int lowestCommonAncestor(BTreeNodeBase* root, int p, int q)
        {
            if (!root)
                return -1;

            TreeListNode* p_head = createPathList(root, p);
            TreeListNode* q_head = createPathList(root, q);
            if (!p_head || !q_head)
                return -1;

            p_head = static_cast<TreeListNode*>(ListUtil::reverseList(p_head));
            q_head = static_cast<TreeListNode*>(ListUtil::reverseList(q_head));
            TreeListNode* common_node = findFirstCommonNode(p_head, q_head);

            if (common_node && common_node->tnode_val)
                return common_node->tnode_val->getKeyVal();
            else
                return -1;
        }

    private:
        /**
         * 以树节点作为值的链表节点
         */
        class TreeListNode : public ListNode
        {
        public:
            TreeListNode(BTreeNodeBase* tree_node)
            {
                if (tree_node)
                    this->val = tree_node->getKeyVal();
            }

            ~TreeListNode() = default;

            BTreeNodeBase* tnode_val = nullptr;
        };

        /**
         * 在二叉搜索树中，创建出从树根到p值节点的搜索路径形成的单链表
         */
        TreeListNode* createPathList(BTreeNodeBase* bst_root, int p)
        {
            if (!bst_root)
                return nullptr;
            TreeListNode* cur = new TreeListNode(bst_root);
            TreeListNode* p_head = cur;

            while (cur != nullptr)
            {
                BTreeNodeBase* cur_tnode = cur->tnode_val;
                if (cur_tnode && cur_tnode->getKeyVal() != p)
                {
                    BTreeNodeBase* next_tnode = p < cur_tnode->getKeyVal()
                                                    ? cur_tnode->getLeftNode()
                                                    : cur_tnode->getRightNode();
                    cur->next = new TreeListNode(next_tnode);
                    cur = static_cast<TreeListNode*>(cur->next);
                }
                else
                    break;
            }
            return p_head;
        }

        /**
         * 在两条树路径形成的单链表中，找到第一个公共的树节点所对应的链表节点
         */
        TreeListNode* findFirstCommonNode(TreeListNode* first_head, TreeListNode* second_head)
        {
            if (!first_head || !second_head)
                return nullptr;

            TreeListNode* first_ptr = first_head;
            bool first_switch_list = false;

            TreeListNode* second_ptr = second_head;
            bool second_switch_list = false;

            while (first_ptr && second_ptr)
            {
                //�״��غϵĽڵ�Ϊ�����ڵ�
                if (first_ptr->tnode_val == second_ptr->tnode_val)
                    return first_ptr;

                first_ptr = static_cast<TreeListNode*>(first_ptr->next);
                if (first_ptr == nullptr && !first_switch_list)
                {
                    first_switch_list = true;
                    first_ptr = second_head;
                }

                second_ptr = static_cast<TreeListNode*>(second_ptr->next);
                if (second_ptr == nullptr && !second_switch_list)
                {
                    second_switch_list = true;
                    second_ptr = first_head;
                }
            }
            return nullptr;
        }
    };

    class RecurMethod
    {
    public:
        /**
         * 递归法:
         *	1、如果p、q都在左子树中，则最近公共祖先可从左子树找到
         *  2、如果p、q都在右子树中，则最近公共祖先可从右子树找到
         *	3、如果上述2个不满足，则p、q一个在左子树中，另外一个在右子树中，或其中一个恰为bst_root,
         *	此时p、q的公共祖先为bst_root.
         */
        BTreeNodeBase* lowestCommonAncestorRecursively(BTreeNodeBase* bst_root, int p, int q)
        {
            if (!bst_root)
                return nullptr;

            if (p < bst_root->getKeyVal() && q < bst_root->getKeyVal())
                return bst_root->getLeftNode()
                           ? lowestCommonAncestorRecursively(bst_root->getLeftNode(), p, q)
                           : bst_root;
            if (p > bst_root->getKeyVal() && q > bst_root->getKeyVal())
                return bst_root->getRightNode()
                           ? lowestCommonAncestorRecursively(bst_root->getRightNode(), p, q)
                           : bst_root;
            return bst_root;
        }
    };

    class Practice:public Question
    {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) override
        {
            if(!root)
                return nullptr;
            if(!p)
                return q;
            if(!q)
                return p;

            if(p->val > q->val)
            {
                TreeNode* tmp=p;
                p=q;
                q=tmp;
            }
            return recurFindLowestCommonAncestor(root,p,q);
        }
    private:
        //输入保证p为值较小的节点,q为值较大的节点,node不为空
        TreeNode* recurFindLowestCommonAncestor(TreeNode* node,TreeNode* p,TreeNode* q)
        {
            if(node->val >= p->val && node->val <= q->val)
                return node;

            //两个节点都比node的值小,去左子树找最低公共祖先
            if(node->val >= p->val && node->val >= q->val)
                return recurFindLowestCommonAncestor(node->left,p,q);

            //两个节点都比node的值大,去右子树找最低公共祖先
            if(node->val <= p->val && node->val <= q->val)
                return recurFindLowestCommonAncestor(node->right,p,q);

            return nullptr;
        }
    };

    TEST(BTreeSharedAnchetorTest, lowestCommonAncestor)
    {
        BTreeNodeBase* bst = TreeUtil::createBTreeFromLayerOrder("{7,1,12,0,4,11,14,#,#,3,5}");
        RecurMethod solution;

        EXPECT_EQ(solution.lowestCommonAncestorRecursively(bst, 1, 12)->getKeyVal(), 7);
        EXPECT_EQ(solution.lowestCommonAncestorRecursively(bst, 12, 11)->getKeyVal(), 12);
    }
}
